package com.gsy.kmp;

import java.text.NumberFormat;
import java.util.Arrays;

public class KMPAlgorithm {
    public static void main(String[] args) {
        char arr[] = new char[10000];
        for (int i = 0; i < arr.length-1; i++) {
            arr[i] = 'a';
        }
        arr[arr.length-1] = 'b';
        String pattern = new String(arr);
        char arr1[] = new char[1000000];
        for (int i = 0; i < arr1.length-1; i++) {
            arr1[i] = 'a';
        }
        arr1[arr1.length-1] = 'b';
        String source = new String(arr1);
//        System.out.println(Arrays.toString(next));
        NumberFormat numberFormat = NumberFormat.getNumberInstance();
        long start  = System.nanoTime();
        int next[] = getNextArr(pattern);
        System.out.println(kmpMatch(source,pattern,next));
        System.out.println("kmp use time = " + numberFormat.format(System.nanoTime() - start) + "ns");
        start = System.nanoTime();
        System.out.println(source.indexOf(pattern));
        System.out.println("java indexOf function = " + numberFormat.format(System.nanoTime() - start) +"ns");
    }
    public static int kmpMatch(String source,String pattern,int next[]){
//        int i = 0;
        int j = 0;
        int i;
        for (i = 0; i < source.length() && j < pattern.length();) {
            if (j == -1 || source.charAt(i) == pattern.charAt(j)){
                j++;
                i++;
            }else {
                j = next[j];
            }
        }
        return j == pattern.length()?(i-j):-1;
    }
    public static int[] getNextArr(String pattern){
        if (pattern == null || pattern.length() ==0) {
            return new int[0];
        }
        int next[] = new int[pattern.length()];
        int j = -1;
        next[0] = -1;
        for (int i = 0; i < pattern.length()-1;) {
            if (j == -1 || pattern.charAt(i) == pattern.charAt(j)) {
                j++;
                i++;
                next[i] = j;
            }else {
                j = next[j];
            }
        }
        return next;
    }
}
